// step 1# 初始化dp数组
int **initDP(int m, int n, int** obstacleGrid) {
    int **dp = (int**)malloc(sizeof(int*) * m);
    int i, j;

    // step 1.1# 初始化每一行的数组
    for(i = 0; i < m; ++i) {
        dp[i] = (int*)malloc(sizeof(int) * n);
    }

    // step 1.2# 先将第一列初始化为0
    for(i = 0; i < m; ++i) {
        dp[i][0] = 0;
    }

    // step 1.3# 先将第一行初始化为0
    for(j = 0; j < n; ++j) {
        dp[0][j] = 0;
    }

    // step 1.4# 处理第一列：遇到障碍后，后面都不能走
    for(i = 0; i < m; ++i) {
        if(obstacleGrid[i][0]) {
            break;
        }
        dp[i][0] = 1;
    }

    // step 1.5# 处理第一行：遇到障碍后，后面都不能走
    for(j = 0; j < n; ++j) {
        if(obstacleGrid[0][j])
            break;
        dp[0][j] = 1;
    }

    // step 1.6# 返回初始化后的dp数组
    return dp;
}

// step 2# 主函数，计算路径数量
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int m = obstacleGridSize, n = *obstacleGridColSize;

    // step 2.1# 初始化dp数组
    int **dp = initDP(m, n, obstacleGrid);

    int i, j;
    // step 2.2# 从(1,1)开始填充dp数组
    for(i = 1; i < m; ++i) {
        for(j = 1; j < n; ++j) {
            // step 2.2.1# 如果当前格子是障碍物，路径为0
            if(obstacleGrid[i][j])
                dp[i][j] = 0;
            // step 2.2.2# 否则路径数等于上方和左方路径数之和
            else
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    // step 2.3# 返回终点(m-1,n-1)的路径数量
    return dp[m-1][n-1];
}
